/**
 * 双向链表节点
 * 用于实现 LRU 缓存，包含 key、value 以及前后指针
 */
class DLinkedNode {
    key: number;
    value: number;
    prev: DLinkedNode | null;
    next: DLinkedNode | null;

    constructor(key?: number, value?: number) {
        this.key = key === undefined ? 0 : key;
        this.value = value === undefined ? 0 : value;
        this.prev = null;
        this.next = null;
    }
}

/**
 * LRU 缓存
 * 实现一个 LRU (Least Recently Used) 缓存机制的数据结构
 * 
 * 算法思路：
 * 使用哈希表 + 双向链表实现：
 * 1. 哈希表：O(1) 时间查找节点
 * 2. 双向链表：O(1) 时间插入和删除节点
 * 3. 最近使用的节点放在链表头部，最久未使用的节点在链表尾部
 * 
 * 时间复杂度：
 * - get: O(1)
 * - put: O(1)
 * 
 * 空间复杂度：O(capacity)，其中 capacity 是缓存的容量
 */
class LRUCache {
    private capacity: number;  // 缓存容量
    private size: number;      // 当前缓存大小
    private cache: Map<number, DLinkedNode>;  // 哈希表，key -> 节点映射
    private head: DLinkedNode;  // 虚拟头节点（哨兵节点）
    private tail: DLinkedNode;  // 虚拟尾节点（哨兵节点）

    constructor(capacity: number) {
        this.capacity = capacity;
        this.size = 0;
        this.cache = new Map();

        // 初始化虚拟头尾节点，简化边界处理
        // 链表结构：head <-> node1 <-> node2 <-> ... <-> tail
        this.head = new DLinkedNode();
        this.tail = new DLinkedNode();
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    /**
     * 获取缓存值
     * 如果 key 存在，返回对应的 value，并将该节点移动到头部（标记为最近使用）
     * 如果 key 不存在，返回 -1
     * 
     * @param key 缓存的键
     * @returns 缓存的值，不存在返回 -1
     */
    get(key: number): number {
        if (!this.cache.has(key)) {
            return -1;
        }

        const node = this.cache.get(key)!;
        // 将访问的节点移动到头部（标记为最近使用）
        this.moveToHead(node);
        return node.value;
    }

    /**
     * 插入或更新缓存
     * 如果 key 已存在，更新其 value 并移动到头部
     * 如果 key 不存在，创建新节点并添加到头部
     * 如果缓存已满，删除尾部节点（最久未使用的节点）
     * 
     * @param key 缓存的键
     * @param value 缓存的值
     */
    put(key: number, value: number): void {
        if (this.cache.has(key)) {
            // 如果 key 已存在，更新值并移动到头部
            const node = this.cache.get(key)!;
            node.value = value;
            this.moveToHead(node);
        } else {
            // 创建新节点
            const newNode = new DLinkedNode(key, value);
            this.cache.set(key, newNode);
            // 添加到链表头部
            this.addToHead(newNode);
            this.size++;

            // 如果超过容量，删除尾部节点（最久未使用的节点）
            if (this.size > this.capacity) {
                const tailNode = this.removeTail();
                this.cache.delete(tailNode.key);
                this.size--;
            }
        }
    }

    /**
     * 将节点添加到链表头部
     * 在 head 和 head.next 之间插入新节点
     * 
     * @param node 要添加的节点
     */
    private addToHead(node: DLinkedNode): void {
        // 设置新节点的前后指针
        node.prev = this.head;
        node.next = this.head.next;
        // 更新原 head.next 的前指针
        this.head.next!.prev = node;
        // 更新 head 的后指针
        this.head.next = node;
    }

    /**
     * 从链表中删除节点
     * 
     * @param node 要删除的节点
     */
    private removeNode(node: DLinkedNode): void {
        // 将节点的前后节点连接起来，跳过当前节点
        node.prev!.next = node.next;
        node.next!.prev = node.prev;
    }

    /**
     * 将节点移动到链表头部
     * 先删除节点，再添加到头部
     * 
     * @param node 要移动的节点
     */
    private moveToHead(node: DLinkedNode): void {
        this.removeNode(node);
        this.addToHead(node);
    }

    /**
     * 删除尾部节点（最久未使用的节点）并返回
     * 
     * @returns 被删除的尾部节点
     */
    private removeTail(): DLinkedNode {
        // tail.prev 是实际的最后一个节点（tail 是虚拟节点）
        const tailNode = this.tail.prev!;
        this.removeNode(tailNode);
        return tailNode;
    }
}